package lcr;

import java.util.*;

public class Test0111 {
    public static void main(String[] args) {
        new Solution0111_1().calcEquation(List.of(List.of("x1","x2"),List.of("x2","x3"),List.of("x3","x4"),List.of("x4","x5")),
                new double[]{3.0,4.0,5.0,6.0},
                List.of(List.of("x2","x4")));
    }
}

class Solution0111_1 {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        HashMap<String, Map<String,Double>> map = new HashMap<>();
        for (int i = 0; i < equations.size(); i++) {
            List<String> strings = equations.get(i);
            String string1 = strings.get(0);
            String string2 = strings.get(1);
            double value = values[i];

            Map<String, Double> map1 = map.getOrDefault(string1, new HashMap<>());
            Map<String, Double> map2 = map.getOrDefault(string2, new HashMap<>());
            map1.put(string2,value);
            map2.put(string1,1/value);
            map.put(string1,map1);
            map.put(string2,map2);
        }

        int size = queries.size();
        double[] ans = new double[size];
        HashSet<String> set = new HashSet<>();
        for (int i = 0; i < size; i++) {
            List<String> query = queries.get(i);
            String v1 = query.get(0);
            String v2 = query.get(1);

            if (v1.equals(v2)) {
                ans[i]=map.get(v1)==null?-1:1;
            }else {
                set.add(v1);
                ans[i]=dfs(set,v1,map,v2,1);
                set.remove(v1);
            }
        }


        return ans;
    }

    public double dfs(Set<String> set, String now,HashMap<String, Map<String,Double>> map,String target,double record){
        Map<String, Double> doubleMap = map.get(now);
        if (doubleMap==null) return -1;

        for (Map.Entry<String, Double> doubleEntry : doubleMap.entrySet()) {
            String key = doubleEntry.getKey();
            Double value = doubleEntry.getValue();
            if (set.contains(key)) continue;
            record*=value;
            if (key.equals(target)) return record;

            set.add(key);
            double result = dfs(set, key, map, target, record);
            set.remove(key);

            if (result>=0) return result;
            record/=value;
        }

        return -1;
    }
}
